package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class FindAllAnagramsInString {

	// 700ms, bad idea
	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> list = new ArrayList<Integer>();
		if (p == null || p.length() <= 0) {
			return list;
		}
		int length = p.length();
		char[] chas = s.toCharArray();
		char[] tChas = p.toCharArray();
		for (int i = 0; i < chas.length;) {
			if (i + length <= chas.length) {
				if (isAnagram(s, tChas, i, i + length)) {
					list.add(i);
					i++;
				} else {
					i++;
				}
			} else {
				return list;
			}
		}
		return list;
	}

	public boolean isAnagram(String s, char[] tChars, int start, int end) {
		// 存储出现的次数
		int[] sCount = new int[26];
		int[] tCount = new int[26];
		char[] sChars = s.substring(start, end).toCharArray();
		for (int i = 0; i < sChars.length; i++) {
			sCount[sChars[i] - 'a']++;
			tCount[tChars[i] - 'a']++;
		}
		for (int i = 0; i < sCount.length; i++) {
			if (sCount[i] != tCount[i]) {
				return false;
			}
		}
		return true;
	}

	//感觉上述的函数调用的代码太慢了
	public List<Integer> findAnagrams2(String s, String t) {
		List<Integer> result = new LinkedList<>();
		if (t.length() > s.length())
			return result;
		Map<Character, Integer> map = new HashMap<>();
		for (char c : t.toCharArray()) {
			map.put(c, map.getOrDefault(c, 0) + 1);
		}
		int counter = map.size();

		int begin = 0, end = 0;
//		int head = 0;
//		int len = Integer.MAX_VALUE;

		while (end < s.length()) {
			char c = s.charAt(end);
			if (map.containsKey(c)) {
				map.put(c, map.get(c) - 1);
				if (map.get(c) == 0)
					counter--;
			}
			end++;

			while (counter == 0) {
				char tempc = s.charAt(begin);
				if (map.containsKey(tempc)) {
					map.put(tempc, map.get(tempc) + 1);
					if (map.get(tempc) > 0) {
						counter++;
					}
				}
				if (end - begin == t.length()) {
					result.add(begin);
				}
				begin++;
			}

		}
		return result;
	}
}
